1. Field
Binary rewriters that do not require relocation information may be relevant to the field of computing. Specifically, such binary rewriters may improve both the functional structure of computer programs and the physical structure of their recording media in a variety of ways.
2. Description of the Related Art
Binary rewriters are tools, often implemented using software running on hardware, that accept a binary executable program as input, and produce an improved executable as output. The output executable usually has the same functionality as the input, but is improved in one or more metrics, such as run-time, energy use, memory use, security, or reliability.
Binary rewriting is valuable even for highly optimized binaries produced by the best industrial-strength compilers. The reasons for this value include the following. Although compilers can in theory do whole-program optimizations, most compile each procedure separately. Moreover, research in whole-program optimization has been focused on a few domains and is limited in general. Binary rewriters have demonstrated inter-procedural optimizations that deliver improvements even on highly optimized binaries. Also, it may be more economically feasible to implement a transformation once in a binary rewriter, rather than repeatedly in each of the many compilers for an instruction set. Additionally, unlike compiler-implemented technology, when a code transformation is implemented in a binary rewriter, it may be applicable to code produced from any programming language, including assembly code, with no additional effort. Finally, binary rewriters can be used to enforce security rules on to-be-executed code. A compiler may not serve to enforce security, since the developer may, maliciously or otherwise, simply not use a compiler with security enforcement.
However the reality is that binary rewriters are not in wide commercial use today. One reason is that conventional binary rewriters are unable to rewrite binaries that have no relocation information. Static, or off-line, rewriters are discussed here, while dynamic, or run-time, rewriters are discussed later. Linkers typically discard relocation information. Indeed, virtually all commercial binaries lack relocation information. Consequently, they cannot be rewritten by existing static rewriters. Instead, developers can rewrite their own binaries by specially generating binaries produced by instructing the linker to retain relocation information. Linkers typically discard relocation and symbolic information because it is not needed for execution, and further, software vendors do not want this information to be revealed for their programs, since it makes it easier to understand and reverse-engineer their products.
Binary rewriting has many applications including inter-procedural optimization, code compaction, security-policy enforcement, preventing control-flow attacks, cache optimization, software caching, and distributed virtual machines for networked computers. Many other code optimizations not listed here are also possible.
The reason for the great interest in research in binary rewriting is that it offers many features that are not conventionally available with compiler-produced optimized binaries. For example, binary rewriters can have the ability to do inter-procedural optimization. Many existing commercial and open-source compilers use separate compilation, i.e., they compile each procedure separately and independently from other procedures. The reason for this separate processing is that programs are typically distributed among several files, and to keep compile times low in the typical repeated debug-recompile cycle during development, it is important to only recompile files that have changed since the last compile. Thus, files are compiled separately. To maintain correctness for functions called across files, this usually implies that functions must also be compiled separately. For example, this is the case with GCC, the most widely used open-source compiler used commercially, even with the highest level of optimization.
In contrast, binary rewriters have access to the entire program, not just one procedure at a time. Hence, unlike in a separate compiler, inter-procedural optimizations become possible.
Another difference between binary rewriters and compilers is increased economic feasibility. It is more economically feasible to implement a code transformation once for an instruction set in a binary rewriter, rather than repeatedly for each compiler for the instruction set. For example, the ARM instruction set has over thirty compilers available for it, and the x86 has a similarly large number of compilers from different vendors and for different source languages. The high expense of repeated compiler implementation often cannot be supported by a small fraction of the demand.
Furthermore, binary compilers can work for code produced from any source language using any compiler. A binary rewriter works for code produced from any source language by any compiler.
Additionally, binary compilers can work for hand-coded assembly routines. Code transformations cannot be applied by a compiler to hand-coded assembly routines, since they are never compiled. In contrast, a binary rewriter can transform such routines.
Consequent to these advantages, a number of binary rewriters, disassemblers and object-code rewriters have been built, mostly in academia. These include IDA, Objdump, Etch, Squeeze and Squeeze++, Dynlnst, OM, ATOM, ALTO, PLTO, Spike, and Diablo.
They are at least two types of binary rewriters: static and dynamic. A conventional static binary rewriter rewrites the binary off-line, but requires relocation (and usually symbolic) information. A conventional dynamic binary rewriter rewrites the binary during its execution, and consequently does not need relocation or symbolic information.
Conventional static binary rewriters need relocation information to be able to distinguish code from data, since rewriting any data that might be buried inside the code section could break correctness. Binaries often contain data in the middle of code. Examples of such data include jump tables, literals, literal tables, alignment bytes, and junk bytes. Relocation and symbolic information can help identify most or all of these data locations, allowing for correct rewriting in most cases. Conventional static rewriters also need relocation information to update indirect branch addresses in light of the target address being moved because of rewriting.
An advantage of dynamic rewriters is that dynamic rewriters do not need relocation information, since at run-time there is no problem distinguishing code from data Consequently, code can be rewritten only when it is about to be executed, at which point it is known to be surely code. Indirect branch addresses may also be known at run-time.
Dynamic binary rewriters conventionally impose the combined overheads of analysis and rewriting at run-time. Thus, conventionally they have been deemed suitable only for simple program transformations, such as instrumentation or localized optimizations. More complex code transformations, such as automatic parallelization, memory management, and inter-procedural optimizations are not deemed to be feasible in a conventional binary rewriter at least because their dynamic compilation overheads would be prohibitive. Moreover, typically only one basic block is rewritten at a time, further limiting the types of possible optimizations. Finally, dynamic rewriters have high run-time overheads even when the application is not rewritten at all, since most dynamic rewriters intercept the applications execution at most indirect branches. Nevertheless, dynamic rewriters have seen some commercial success, such as in the use of DynamoRIO by Determina® Inc. (subsequently purchased by VMWare®) for its security checks on control-flow.
Existing dynamic binary rewriters are not used to rewrite a binary file into a rewritten binary file that works for all input data sets for the binary. Instead existing dynamic rewriters rewrite code discovered for a particular input data set to main memory. This rewritten code in main memory may not be complete, since with a different data set the program may discover new code that was not discovered with an earlier data set. Thus, because a dynamic binary rewriter is not a static binary rewriter, the dynamic binary rewriter is not designed to rewrite programs off-line without having access to any data set, and is not designed to provide an output binary that is configured to work for all input data sets. Indeed, existing dynamic rewriters cannot provide such an output binary file.